import java.util.*;
public class RandomizedQuickSort 
{
	public static void exchange(int[] A, int i, int j)
	{
		int temp=0;
		temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
	
	public static int random(int p, int r)
	{
		return (int)(p + Math.random()*(r - p + 1));
	}
	
	public static int randomizedPartition(int[] A, int p, int r)
	{
		int i = p-1,j=p;
		exchange(A,random(p,r),r);
		for(j=p; j<r; j++)
		{
			if(A[j] < A[r])
			{
				i++;
				exchange(A,i,j);
			}
		}
		exchange(A,++i,r);
		return i;
	}
	
	public static void randomizedQuickSort(int[] A, int p, int r)
	{
		int m=0;
		if (p < r)
		{
			m = randomizedPartition(A, p, r);
			randomizedQuickSort(A, p, m-1);
			randomizedQuickSort(A, m+1, r);
		}
	}
	
	public static void main(String[] args)
	{
		int[] A = {0,4,1,3,2,16,9,10,14,8,7};
		randomizedQuickSort(A, 1, 10);
		System.out.println(Arrays.toString(A));
	}

}
